package 代码随想录_回溯.力扣_回溯.搜索矩阵;

/**回溯算法
 * @author zx
 * @create 2022-05-28 23:25
 * 题目改了 - LCR 129.字母迷宫  or  79. 单词搜索
 */
public class 矩阵中的路径_12 {
    public boolean exist(char[][] board, String word) {
        for(int i = 0; i < board.length; i++) {
            for(int j = 0; j < board[0].length; j++) {
                if(dfs(board, word, i, j, 0)) {
                    return true;
                }
            }
        }
        return false;
    }
    //上下左右四个方向找,"找到完整的word后"返回true.注意边界条件,"超出边界"或"所在位置元素不满足条件"则返回false
    private boolean dfs(char[][] board, String word, int i, int j, int k) {
        //超出边界或所在位置元素不满足条件则返回false
        if(i < 0 || i >= board.length || j < 0 || j >= board[0].length){
            return false;
        }
        // 当前矩阵元素与目标字符不同
        if(board[i][j] != word.charAt(k)){
            return false;
        }
        // 字符串word已全部匹配
        if(k == word.length() - 1) {
            return true;
        }
        // 将board[i][j]修改为' ',代表此元素已访问过
        board[i][j] = ' ';
        //四个方向搜索(约束条件都在前面过滤掉了)
        boolean res = dfs(board, word, i + 1, j, k + 1) ||
                dfs(board, word, i - 1, j, k + 1) ||
                dfs(board, word, i, j + 1, k + 1) ||
                dfs(board, word, i , j - 1, k + 1);
        // 回溯：将board[i][j]元素还原至初始值,即word[k]
        board[i][j] = word.charAt(k);
        return res;
    }
}
